区间dp 置顶 | 发布于 2020-07-11 | 分类于 dp 、 区间dp | 19分钟 | 3285字数 一.概念 对于一段区间求最优解,且该区间可以分为几个小区间的最优解合并(最优子结构)。 二.基本思路 阅读全文 »
伯努利数 置顶 | 发布于 2020-07-11 | 分类于 数学 、 伯努利数 | 8分钟 | 1346字数 伯努利数是一个用于解决 nnn 次方和的数列。 它的递归定义公式如下: ∑i=0n(n+1i)Bi=[n=0] (1.1)\sum_{i=0}^n \binom {n+1}{i} B_i=[n=0] ~~~~~~~~ (1.1) 阅读全文 »
数论函数综合 置顶 | 发布于 2020-07-05 | 分类于 数论 、 莫比乌斯反演 | 22分钟 | 3889字数 一.数论函数 1.定义 数论函数是 : 其定义域是正整数,值域是一个数集的函数。 阅读全文 »
AT4434 [ARC103D] Distance Sums 发布于 2021-02-01 | 分类于 构造 | 4分钟 | 539字数 由题显然有: {sizu=1+∑v∈sonusizvdv=du+n−2×sizv\begin{cases} 阅读全文 »
P6825 「EZEC-4」求和 发布于 2021-02-01 | 分类于 莫比乌斯反演 | 3分钟 | 466字数 ∑i=1n∑j=1ngcd(i,j)i+j\sum_{i=1}^n \sum_{j=1}^n \gcd(i,j)^{i+j} i=1∑nj=1∑ngcd(i,j)i+j ∑d=1n∑i=1n∑j=1n[gcd(i,j)=d]di+j\sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^n [\gcd(i,j)=d]d^{i+j} 阅读全文 »
CF547C Mike and Foam 发布于 2021-02-01 | 分类于 莫比乌斯反演 | 4分钟 | 671字数 记 cic_ici 为 iii 毫升泡沫的酒在架子上的瓶数,A=maxi=1naiA=\max_{i=1}^n a_iA=maxi=1nai。 为了方便将二元组视为有序,答案除以 222 即可。 ∑i=1A∑j=1Acicj[gcd(i,j)=1]\sum_{i=1}^A \sum_{j=1}^A c_i c_j [\gcd(i,j)=1] 阅读全文 »
CF900D Unusual Sequences 发布于 2021-02-01 | 分类于 组合数学 、 莫比乌斯反演 | 4分钟 | 602字数 建议先做 CF439E。 ∑n=1y∑i1=1y∑i2=1y...∑in=1y[∑ai=y][gcdai=x]\sum_{n=1}^y\sum_{i_1=1}^y\sum_{i_2=1}^y...\sum_{i_n=1}^y [\sum{a_i}=y][\gcd{a_i}=x] n=1∑yi1=1∑yi2=1∑y...in=1∑y[∑ai=y][gcdai=x] 阅读全文 »
CF439E Devu and Birthday Celebration 发布于 2021-02-01 | 分类于 组合数学 、 莫比乌斯反演 | 4分钟 | 511字数 ∑i1=1n∑i2=1n...∑if=1n[∑ai=n][gcdai=1]\sum_{i_1=1}^n\sum_{i_2=1}^n...\sum_{i_f=1}^n [\sum{a_i}=n][\gcd{a_i}=1] i1=1∑ni2=1∑n...if=1∑n[∑ai=n][gcdai=1] ∑i1=1n∑i2=1n...∑if=1n[∑ai=n]∑d∣gcdaiμ(d)\sum_{i_1=1}^n\sum_{i_2=1}^n...\sum_{i_f=1}^n [\sum{a_i}=n]\sum_{d|\gcd{a_i}} \mu(d) 阅读全文 »